package sort.swap_sort;

import java.util.Arrays;

/**
 * 时间复杂度：<br />
 * 最好：O(n * logn), 即每次都能平分数组 <br />
 * 最坏：O(n * n), 数组基本有序 <br />
 * 不稳定
 *
 * @author yzh
 * @data 2021/3/25 10:32
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {3, -44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
//        quickSort(nums, 0, nums.length - 1);
//        kuaisu(nums, 0, nums.length - 1);
        anotherQuickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    public static void kuaisu(int[] nums, int begin, int end) {
        if (begin >= end) return;
        int left = begin, right = end;
        while (left < right) {
            while (left < right && nums[right] >= nums[begin]) --right;
            while (left < right && nums[left] < nums[begin]) ++left;
            swap(nums, left, right);
        }
        swap(nums, begin, left);
        kuaisu(nums, begin, left - 1);
        kuaisu(nums, left + 1, end);
    }

    /**
     * 取数组的第一个数字为基准数，比这个数字大的往后，小的往前
     * 这样，每次执行就会把数组分成两个部分，依次递归
     *
     * @param nums
     * @param begin
     * @param end
     */
    public static void quickSort(int[] nums, int begin, int end) {
        if (begin >= end) return;
        int left = begin, right = end;
        while (left < right) {
            while (left < right && nums[right] >= nums[begin]) --right;
            while (left < right && nums[left] < nums[begin]) ++left;
            int tem = nums[left];
            nums[left] = nums[right];
            nums[right] = tem;
        }
        int tem = nums[begin];
        nums[begin] = nums[left];
        nums[left] = tem;
        quickSort(nums, 0, left - 1);
        quickSort(nums, left + 1, end);
    }

    /**
     * 书上的写法
     */
    public static void anotherQuickSort(int[] nums, int begin, int end) {
        if (begin >= end) return;
        int first = nums[begin], i = begin, j = end;
        while (i < j) {
            // 这一步可能会导致不稳定, 例如 (0, 2) (1, 1) (2, 1) -> (2, 1) (1, 1) (0, 2)
            while (i < j && nums[j] >= first) --j;
            swap(nums, i, j);
            // 这一步可能会导致不稳定
            while (i < j && nums[i] < first) ++i;
            swap(nums, i, j);
        }
        nums[i] = first;
        anotherQuickSort(nums, begin, i - 1);
        anotherQuickSort(nums, i + 1, end);
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
